In implementations of programming languages that support dynamic object allocation, it is sometimes necessary to perform an operation on a possibly large subset of the objects in the heap atomically with respect to the application threads that are accessing the objects. In this context, performing an operation atomically means that one group of threads working on a particular task first selects a subset of the objects in the heap in accordance with some criteria and then obtains exclusive access to the subset of objects for a period of time, isolating that subset of objects from threads outside of the one group for all, or at least part of the time period. During the time period an operation is performed on all of the objects in the subset.
One example of such an operation on selected objects is object relocation. Garbage collectors relocate existing objects and update all references to the relocated objects to reflect their new location. If this relocation operation is not done atomically, different application threads might access both the original object and the relocated object, which will create inconsistencies.
Another example of an atomic operation that can be applied to a subset of objects is schema evolution. In many database management systems, the structure of each database table is defined by a schema. Similarly, in object-oriented programs, each object is defined by a class from which the object is constructed. Object definitions make it possible to make modifications in all objects of a given type simply by modifying the schema. In some cases, the structure of all existing objects of a given type might be changed to reflect a change in the definition of that type. For example, a new field might be added to an object class and it may be necessary to change all existing instances of that class to reflect this change. It is important that these changes be made atomically since, typically, it is important that an application access exactly one version of a given object type.
Still other examples of operations that require atomicity are operations performed by sampling and debugging applications. In performing queries about the behavior of running applications, sampling and debugging applications typically generate a snapshot of the state of some subset of objects in the heap.
The most common conventional method to achieve the required atomicity is to first stop all application threads. Then, the operation is performed on the selected sub-set of objects and finally, all application threads are restarted. Thus, the application threads see one version of the heap just before they are stopped, and after they are restarted they see a new version of the heap, with the operation in question completed. This type of staged operation is often called a “stop-the-world” (STW) operation. For example, most relocating garbage collectors, such as copying garbage collectors and sliding-compacting garbage collectors, perform object relocation in a STW fashion. Specifically, all application threads are stopped, live objects are relocated and all references to them updated. When the application threads are restarted, any reference that they might access is guaranteed to have been updated to reflect the new location of the corresponding object.
However, such STW pauses can be quite long and some applications, such as real-time or interactive applications, cannot tolerate long pauses. Therefore, it is sometimes desirable to perform the atomic operations concurrently, or mostly concurrently, with the operation of the application threads. This requires the atomic operation to be synchronized with the application threads. Synchronizing the atomic operation with the application threads is typically achieved by introducing an explicit “barrier” for all read operations, for all write operations, or for both read and write operations. These barriers operate when an application thread attempts to access an object while the atomic operation is in progress (being performed by another thread). During this attempt, the barrier checks whether the atomic operation has been completed on the object in question. If it has, then the barrier can allow the application thread to access the object. If the atomic operation has not completed, then the barrier can either perform the atomic operation eagerly or wait until another thread completes it.
Since read barriers must typically be added to each dereferencing operation in which a value is obtained by reading the memory at the address of the pointer, they are considered especially expensive (at least a 4% to 10% overhead). Consequently, some effort is made to avoid them or, at least ameliorate the effects. For example, some garbage collectors use write barriers together with an access barrier and an indirection pointer to the current copy of an object. Although such collectors are said to not use read barriers, they effectively incur the same overhead due to the use of an indirection pointer. Other known schemes use specialized hardware to implement the barriers thereby decreasing the overhead cost incurred by software implementations. However, such schemes have not been widely adopted. Other problems with barriers are that they apply to all objects in the heap, even though only a sub-set of the objects will be processed by the atomic operation and, conventionally, they are constantly enabled even though they are only needed when objects are being transformed.